package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/6/4 9:35
 **/
public class MinimumFallingPathSum931 {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        int[] f = new int[n+2];
        f[0] = f[n+1] = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++) f[j] = matrix[0][j-1];
        for(int i = 1; i < m;i++){
            int temp = 0,last = Integer.MAX_VALUE;
            for(int j = 1; j <= n; j++){
                temp = f[j];
                f[j] = Math.min(Math.min(last,f[j]),f[j+1])+matrix[i][j-1];
                last = temp;
            }
        }
        int min = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++) min = Math.min(min,f[j]);
        return min;
    }

    public int minFallingPathSum2(int[][] A) {
        int N = A.length;
        for (int r = N-2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                int best = A[r+1][c];
                if (c > 0)
                    best = Math.min(best, A[r+1][c-1]);
                if (c+1 < N)
                    best = Math.min(best, A[r+1][c+1]);
                A[r][c] += best;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int x: A[0])
            ans = Math.min(ans, x);
        return ans;
    }

    public int minFallingPathSum3(int[][] matrix) {
        int n = matrix.length;
        //dp[i][j] 表示 到达该点的最小值
        int[][] dp = new int[n][n];
        //初始化
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i];
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < n; j++){
                //对j=0 和 j=n-1 分别处理
                if(j == 0){
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];
                }else if (j == n-1){
                    dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1])+matrix[i][j];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+matrix[i][j];
                }

            }
        }
        int min = dp[n-1][0];
        for(int i = 1; i < n; i++){
            min = Math.min(min,dp[n-1][i]);
        }
        return min;
    }

}
